# 10:30

import unittest
from itertools import starmap, count
import math

def isqrt(x):
	return int(math.sqrt(x)+1)

def is_prime(x):
	factors = [i for i in range(2,isqrt(x)) if x%i==0]
	return len(factors)==0

def max_primes(n):
	return filter(is_prime, range(1,n+1))

def mod_six(n):
	return n%6==0

primes = set(max_primes(10002))
_6k_plus1 = set(p for p in primes if mod_six(p-1) )
_6k_minus1 = set(p for p in primes if mod_six(p+1) )

directions = [(1,0), (0,-1), (-1,0), (0,1)]

def step_on(position, current_direction):
	new_position = starmap(int.__add__, zip(position, current_direction))
	return tuple(new_position)

def update(n, current_direction):
	direction_index = directions.index(current_direction)
	if n in _6k_plus1: 
		new_index = (direction_index-1)%4
		return directions[new_index]
	elif n in _6k_minus1:
		new_index = (direction_index+1)%4
		return directions[new_index]
	return current_direction

def gruen_path():
	position = (0,0)
	direction = directions[0]
	for i in count(3,2):
		yield i,position
		if i in primes:
			direction = update(i, direction)
		position = step_on(position, direction)

def crossing(top=1002):
	rec = dict()
	for n,p in gruen_path():
		if n>top: break
		rec[p] = rec[p]+[n] if rec.get(p) else [n]
	return rec.values()

class TDD(unittest.TestCase):

	def test_isprime(self):
		self.assertTrue( is_prime(5) )
		self.assertTrue( is_prime(3) )
		self.assertTrue( is_prime(2) )
		[self.assertFalse( is_prime(i) ) for i in range(4,200,2)]

	def test_max_primes(self):
		known_primes = [1,2,3,5,7,11,13,17]
		self.assertEquals(list(max_primes(17)),known_primes)

	def test_step_on(self):
		position = 0,0
		one_step = step_on(position, (1,0))
		self.assertEquals( one_step, (1,0) )
	
	def test_update(self):
		current_direction = (0,1)
		self.assertEquals( update(5, current_direction), (1,0) )
		self.assertEquals( update(7, current_direction), (-1,0) )

	def test_path(self):
		gen = gruen_path()
		i,p = next(gen)
		self.assertEquals(i,3)
		self.assertEquals(p,(0,0))

		i,p = next(gen)
		self.assertEquals(i,5)
		self.assertEquals(p,(1,0))

		i,p = next(gen)
		self.assertEquals(i,7)
		self.assertEquals(p,(1,-1))
		
		i,p = next(gen)
		self.assertEquals(i,9)
		self.assertEquals(p,(2,-1))

	def test_crossing(self):
		self.assertIn([137,337], crossing())
		

if __name__ == "__main__":
	unittest.main()
